\documentclass[11pt,titlepaage,a4paper]{report}
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{verbatim}
\usepackage{listings}
\newcommand{\HRule}{\rule{\linewidth}{0.5mm}}



%\title{Projet Hexxagon\\Partie MOIA}
%\author{Sophie Teixeira \and Alex Ginhoux}
%\date{13 mai 2013}

\begin{document}

\input{titlepage_MOIA}


\tableofcontents

\input{presentation_Hexxagon}

\chapter{Implémentation}
Le but de ce projet étant d'appliquer nos connaissances acquises sur le langage Prolog \footnote{Prolog est un langage de programmation informatique utilisant le paradigme logique}, nous avons réalisé la partie intelligence artificielle (I.A) à l'aide de ce langage. Nous avons réalisé deux algorithmes.
En effet, nous avons beaucoup de mal à construire un algorithme permettant de donner un coup  "intelligent" en moins de 6 secondes. Nous avons donc commencé par faire une stratégie dite "random" qui donnait un coup aléatoirement. Son algorithme est simple: on calcule tous les coups valide pouvant être joué, puis nous tirons un coup au hazard et nous le retournons. Cependant, ayant finalement réussi à construire un algorithme répondant aux attentes nous allons plutôt présenté ce second algorithme dans cette partie.

\section{Présentation des structures}

\subsection*{Les joueurs}

Les joueurs sont pour nous des entités pouvant détenir des pions. Nous avons donc trois entités au total : 
\begin{itemize}
\item Le joueur simulé par l'I.A
\item L'adversaire
\item Le plateau
\end{itemize}
Pour ces trois entités, nous avons défini des constantes. Le joueur simulé par l'I.A correspond à la constante "\texttt{j}", l'adversaire à la constante "\texttt{a}", et le plateau à la constante "\texttt{m}".

\subsection*{Les pions}
Dans le langage Prolog nous avons décidé de représenter un pion sous la forme d'une liste comportant la position en abscisse, la position en ordonnée et le propriétaire de ce pion. Les pions sont donc de la forme :
 \begin{lstlisting}[language=Prolog]
[0,0,j]
\end{lstlisting}

\subsection*{Les coordonnées}
La figure \ref{plateau} présente les coordonnées des cases du plateau selon la description donnée dans l'énoncé du sujet. Ce sont également les coordonnées gérées par l'arbitre. Cependant, pour notre implémentation en Prolog, nous avons décidé de garder les mêmes axes pour les abscisses et les ordonnées, mais les valeurs vont de -4 à 4 (pour les abscisses et les ordonnées). Cette numérotation positionne la coordonnée [0,0] au centre du plateau. La figure \ref{coordonnes_nous} présente notre numérotation des axes.

\subsection*{Le plateau}
\label{plateau_exp}
Nous avons choisi de représenter le plateau sous la forme d'une liste où chaque élément est une case appartenant à une entité. Nous ne listons donc pas les cases vides, mais nous listons les cases appartenant au plateau (les cases invalides sont présentées sur la figure \ref{initplateau} page \pageref{initplateau}). Ainsi, le plateau suivant est valide selon notre spécification :
 \begin{lstlisting}[language=Prolog]
[[0,0,j],[1,1,m],[-1,0,m],[0,-1,m]]
\end{lstlisting}
Sur ce plateau se situe un seul pion appartenant au joueur simulé par l'I.A. en position centrale.
\begin{figure}
\center
   \caption{\label{coordonnes_nous} La numérotation de nos axes tel que utilisé en Prolog}
\includegraphics[scale=0.5]{images/numerotation_nous}
\end{figure}

\subsection*{Les coups}
 Un coup représente un mouvement possible par un joueur. Nous le représentons par une liste de deux éléments :
\begin{itemize}
\item Le pion source
\item La liste des pions d'arrivées
\end{itemize}
Le pion source est le pion joué par le joueur. Ce pion se situe sur le plateau avant le jeu. La liste des pions d'arrivée représente la liste des pions situés sur le plateau après le coup. Ainsi dans le cas d'un déplacement de type saut (respectivement duplication), la liste des pions d'arrivées ne comporte qu'un seul élément (resp. deux). Ainsi, les deux coups représentés par les figures \ref{premouvement} et \ref{postmouvement} sont représentés comme suit pour le saut :
 \begin{lstlisting}[language=Prolog]
[[-1,1,j],[[-3,1, j]]]
\end{lstlisting}
et pour la duplication :
 \begin{lstlisting}[language=Prolog]
[[1,-2,j],[[1,-2,j],[1,-3, j]]]
\end{lstlisting}


\section{Stratégie}
Notre stratégie se base sur la simulation exhaustive des possibilités. Nous calculons tous les mouvements qui s'offrent au joueur. Pour chacun des tableaux (nommés tableaux du joueur) obtenu, nous calculons tous les déplacement possible pour l'adversaire. Ensuite, nous donnons une note à ces tableaux (nommées tableaux de l'adversaire). Puis nous calculons la moyenne des notes obtenus par tous les tableaux de l'adversaire correspondant à un meme tableau du joueur.
Ainsi, nous obtenons une note pour chaque tableau correspondant à un mouvement du joueur. Nous pouvons donc déterminer la meilleur de ces notes qui correspond au meilleur mouvement possible pour le joueur. Cette décomposition de l'algorithme est représenté par la figure \ref{strategie}. 

\begin{figure}
	\center
   \caption{\label{strategie} Décomposition de notre stratégie}
\includegraphics[scale=0.7]{images/strategie2}
\end{figure}

\subsection*{Calcul de la note}
Chaque mouvement de l'adversaire donne un nouveau plateau. Afin de pouvoir les comparer, nous leur donnons une note. Plus la note est élevée, meilleure est la disposition du plateau du point de vue du joueur. Pour calculer la note nous utilisons deux valeurs :
\begin{description}
\item[nbJ:] Le nombre de pions appartenant au joueur.
\item[nbA:] Le nombre de pions appartenant à l'adversaire.
\end{description}
Ensuite nous nous sommes basé sur des théories:
\begin{itemize}
\item le joueur a intérêt à avoir le plus de pions possible
\item le joueur a intérêt à avoir plus de pions que l'adversaire.
\end{itemize}
De tout cela, nous en avons déduis une formule:
\[
   Note = NbJ -  NbA
\]
Ainsi, en considérant que le joueur simulé par l'IA est le détenteur des pions rouges, le plateau représenté par la figure \ref{plateauexemple} obtient une note de 0.
\begin{figure}
	\center
   \caption{\label{plateauexemple} Un exemple de plateau où les cases protégées sont marquées par un P}
\includegraphics[scale=0.5]{images/exempleplateau}
\end{figure}

Idéalement, nous pensions utiliser une notation utilisant le nombre de pion protégé (qui ne peuvent être repris). En considérant NbPJ (respectivement NbPA) le nombre de pion protégé, appartenant au joueur (resp. à l'adversaire) La formule aurait été:

\[
   Note = ((NbPJ *2 ) + NbJ) - (NbA + (2*NbPA))
\]

Cependant, le calcul des pions protégé est trop lent et ralentit considérablement le calcul.

 \section{Prédicats important}
Notre code étant documenté, nous allons uniquement présenté les prédicats d'entrée, c'est à dire les prédicats qu'il faut appeler pour éxécuter l'Intelligence Artificielle.
Les principaux prédicats sont:
\begin{description}
\item[initPlateau/2:] Ce prédicat permet de construire un plateau initialisé pour le jeu Hexxagon. Ce prédicat prend deux paramètre dont le premier est le joueur qui possède les pions rouges. Il retourne le plateau initialisé dans le second paramètre.

\item[run/6:] Ce prédicat prend 6 paramètres. Le premier paramètre est un plateau du jeu Hexxagon comme décrit dans la partie \ref{plateau_exp}. Il retourne dans l'ordre suivant:
\begin{enumerate}
\item Le pion source à jouer pour faire le meilleur coup.
\item Le pion destination où déplacer le pion source.
\item Le plateau provoqué par le mouvement.
\item le type de coup ( Duplication, saut, gagne, perd, nulle).
\item determine si le joueur est bloque apres ce coup.
\end{enumerate}

\item[run\_random/6:]Ce prédicat fait la même chose que run6. Seule la stratégie differe (et donc le résultat).

\item[applique\_coup\_java/4:]  applique un coup sur un plateau donné. Le nouveau plateau est retourné via le quatrième paramètre. Les paramètres sont les suivants:
\begin{enumerate}
\item La coordonnée source du déplacement
\item La coordonnée destination du déplacement
\item Le plateau sur lequel est joué le déplacement
\item Le nouveau plateau après le déplacement.
\end{enumerate}

\end{description}


\end{document}
